#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
		size_t lenNo1 = 0;
		for(size_t i=0;i<digits.size();i++)
		{
			if(digits[i] != '1')
				lenNo1++;
		}


		vector<string> result;
		if(digits.empty() || lenNo1==0)
		{

			result.push_back("");
			return result;
		}

		string tmp(lenNo1,'\0');
		solve(0,0,digits,tmp,result);

		return result;
    }

	void solve(size_t srcIdx,size_t destIdx,const string& digits,string& curTmp,vector<string>& result)
	{
		static const char* Maps [] = 
		{
			"abc",
			"def",
			"ghi",
			"jkl",
			"mno",
			"pqrs",
			"tuv",
			"wxyz"
		};
		if(srcIdx >= digits.size())
		{
			result.push_back(curTmp);
			return;
		}

		if(digits[srcIdx] == '1')
			solve(srcIdx+1,destIdx,digits,curTmp,result);

		
		const char* curDigits = Maps[digits[srcIdx]-'2'];

		while(*curDigits)
		{
			curTmp[destIdx] = *curDigits;
			solve(srcIdx+1,destIdx+1,digits,curTmp,result);
			curDigits++;
		}
	}
};
#endif